package main;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Map.Entry;


public class BinaryTree {

	private BinaryNode head;
	private String order;
	private HashMap<Character, String> compressionCodes;
	private HashMap<String, String> decompressionCodes;
	
	public BinaryTree(String order){
		this.buildTree(order);
	}
	
	public BinaryTree(LinkedList<Entry<Character, Integer>> list){
		
		LinkedList<BinaryNode> newNodes = new LinkedList<BinaryNode>();
		
		while(newNodes.size()+list.size() >1){
			int listFirst = list.size()>0?list.getFirst().getValue():Integer.MAX_VALUE;
			int listSecond = list.size()>1?list.get(1).getValue():Integer.MAX_VALUE;
			int newNodesFirst = newNodes.size()>0?newNodes.getFirst().getWeight():Integer.MAX_VALUE;
			int NewNodesSecond = newNodes.size()>1?newNodes.get(1).getWeight():Integer.MAX_VALUE;
			
			long listFirstSecond = (long)listFirst+(long)listSecond;
			long newNodeFirstSecond = (long)newNodesFirst+(long)NewNodesSecond;
			long listFirstNodeFirst = (long)newNodesFirst+(long)listFirst;
			
			if(listFirstSecond < newNodeFirstSecond && listFirstSecond < listFirstNodeFirst)
			{
				Entry<Character, Integer> e = list.removeFirst();
				Entry<Character, Integer> e2 = list.removeFirst();
				newNodes.addLast(new BinaryNode((char)0, listFirst+listSecond, new BinaryNode(e.getKey(), e.getValue(), null, null,false), new BinaryNode(e2.getKey(), e2.getValue(), null, null,false),true));
			}else if(listFirstNodeFirst < newNodeFirstSecond)
			{
				Entry<Character, Integer> e = list.removeFirst();
				BinaryNode n = newNodes.removeFirst();
				newNodes.addLast(new BinaryNode((char)0, listFirst+listSecond, new BinaryNode(e.getKey(), e.getValue(), null, null, false), n, true));
			}else
			{
				BinaryNode n = newNodes.removeFirst();
				BinaryNode n2 = newNodes.removeFirst();
				newNodes.addLast(new BinaryNode((char)0, listFirst+listSecond, n2, n, true));
			}

		}
		
		head = newNodes.removeFirst();
		compressionCodes = genCompressionCodes();
		order = genOrder();
			
	}
	
	public BinaryNode getHead(){
		return head;
	}
	
	public String print(BinaryNode bn){
		String result = "";
		if(bn.getZero() != null){
			result += "|" + print(bn.getZero());
		}
		if(bn.getOne() != null){
			result += "|" + print(bn.getOne());
		}
		if(bn.getZero() == null && bn.getOne() == null){
			return bn.getChar() + ":" + bn.getWeight(); 
		}
		return result;
	}
	
	public String print(){

		return print(head);
	}
	
	private HashMap<Character, String> genCompressionCodes(){
		BinaryNode now = head;
		HashMap<Character, String> codes = new HashMap<Character, String>();
		StringBuilder sb = new StringBuilder();
		Stack<BinaryNode> stack = new Stack<BinaryNode>();
		
		while(now != null){
			if(now.getZero() != null && !now.getZero().visited()){
				stack.push(now);
				now = now.getZero();
				sb.append('0');
			}else if(now.getOne() != null && !now.getOne().visited()){
				stack.push(now);
				now = now.getOne();
				sb.append('1');
			}

			if(now.getZero() == null && now.getOne() == null || now.getZero().visited() && now.getOne().visited()){
				if(now != null && !now.nil()){
					codes.put(now.getChar(), sb.toString());					
				}
				now.setVisited(true);
				now = stack.size()>0?stack.pop():null;
				if(sb.length() > 0){
					sb.deleteCharAt(sb.length()-1);
				}
			}
		}
		return codes;
	}
	
	private String genOrder(){
		BinaryNode now = head;
		HashMap<Character, String> codes = new HashMap<Character, String>();
		StringBuilder sb = new StringBuilder();
		Stack<BinaryNode> stack = new Stack<BinaryNode>();
		
		while(now != null){
			if(now.getZero() != null && now.getZero().visited()){
				stack.push(now);
				now = now.getZero();
			}else if(now.getOne() != null && now.getOne().visited()){
				stack.push(now);
				now = now.getOne();
			}
			
			if(now.getZero() == null && now.getOne() == null || !now.getZero().visited() && !now.getOne().visited()){
				codes.put(now.getChar(), sb.toString());
				if(now != null && !now.nil()){
					sb.append(now.getChar());					
				}else{
					sb.append("-:");
				}
				now.setVisited(false);
				now = stack.size()>0?stack.pop():null;

			}
		}
		return sb.reverse().toString();
	}
	
	private void buildTree(String order){
		char[] chars = order.toCharArray();

		Stack<BinaryNode> stack = new Stack<BinaryNode>();
		BinaryNode newNode;
		this.head = new BinaryNode((char)0, 0, null, null, true);
		stack.push(head);
		for(int i = 2; i < chars.length;i++){
			if(chars[i] == ':' && chars[i+1] == '-'){
				newNode = new BinaryNode((char)0, 0, null, null, true);
				if(stack.peek().getOne()==null){
					stack.peek().setOne(newNode);
				}else if(stack.peek().getZero() == null){
					stack.pop().setZero(newNode);
				}
				stack.push(newNode);
				i++;
			}else{
				if(stack.peek().getOne()==null){
					stack.peek().setOne(new BinaryNode(chars[i], 0, null, null, false));
				}else if(stack.peek().getZero() == null){
					stack.pop().setZero(new BinaryNode(chars[i], 0, null, null, false));
				}
			}
		}		
		decompressionCodes = genDecompressionCodes();
		this.order = genOrder();

	}
	
	public HashMap<Character, String> getCompressionCodes(){
		return this.compressionCodes;
	}
	
	public HashMap<String, String> getDecompressionCodes(){
		return this.decompressionCodes;
	}
	
	public String getOrder(){
		return this.order;
	}
	
	private HashMap<String, String> genDecompressionCodes(){
		BinaryNode now = head;
		HashMap<String, String> codes = new HashMap<String, String>();
		StringBuilder sb = new StringBuilder();
		Stack<BinaryNode> stack = new Stack<BinaryNode>();
		
		while(now != null){
			if(now.getZero() != null && !now.getZero().visited()){
				stack.push(now);
				now = now.getZero();
				sb.append('0');
			}else if(now.getOne() != null && !now.getOne().visited()){
				stack.push(now);
				now = now.getOne();
				sb.append('1');
			}
			
			if(now.getZero() == null && now.getOne() == null || now.getZero().visited() && now.getOne().visited()){
				if(now != null && !now.nil()){
					codes.put(sb.toString(), String.valueOf(now.getChar()));					
				}
				now.setVisited(true);
				now = stack.size()>0?stack.pop():null;
				if(sb.length() > 0){
					sb.deleteCharAt(sb.length()-1);
				}
			}
		}
		return codes;
	}
}
